#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

void swap(int arr[], int i, int j)
{
	int tmp = arr[i];
	arr[i] = arr[j];
	arr[j] = tmp;
}
int partition(int arr[], int L, int R)
{
	int i = L;
	int j = R;
	int v = arr[L];
	while (i != j)
	{
		while (arr[j] >= v && j > i)
		{
			j--;
		}
		while (arr[i] <= v && j > i)
		{
			i++;
		}
		if (j > i)
		{
			swap(arr, i, j);
		}
	}
	swap(arr, L, j);
}

void qSort(int arr[], int L, int R)
{
	if (L >= R)
	{
		return;
	}
	int j = partition(arr, L, R);
	qSort(arr, L, j - 1);
	qSort(arr, j + 1, R);
}


void print(int arr[], int len)
{
	for (int i = 0; i < len; i++)
	{
		printf("%d ", arr[i]);
	}
}
int main()
{
	int arr[15] = { 7,3,1,2,2,4,5,5,9,8,10,6,17,20,100};
	int len = sizeof(arr) / sizeof(arr[0]);
	qSort(arr, 0, len - 1);
	print(arr, len);
	return 0;
}